

#  1049.最后一块石头的重量II

def lastStoneWeightII(stones):
    """
    :type stones: List[int]
    :rtype: int
    """
    wight = sum(stones) // 2
    if sum(stones) % 2 != 0:
        wights = wight + 1
    else:
        wights = wight
    dp = [[None]*(wight+1) for _ in range(0,len(stones))]
    for i in range(0, len(stones)):
        dp[i][0] = 0
    if stones[0] > wight:
        for j in range(0, wight + 1):
            dp[0][j] = 0
    else:
        for j in range(0, stones[0]):
            dp[0][j] = 0
        for j in range(stones[0], wight + 1):
            dp[0][j] = stones[0]
    for i in range(1, len(stones)):
        for j in range(1, wight + 1):
            if j < stones[i]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i])
    print(dp)
    return wights - dp[len(stones) - 1][wight]


if __name__ == "__main__":
    lastStoneWeightII([31,26,33,21,40])